package ch.ethz.fcl.metrobuzz.algorithm.network.all_simple_paths;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import ch.ethz.fcl.metrobuzz.algorithm.network.Path;
import ch.ethz.fcl.metrobuzz.data.MBData;
import ch.ethz.fcl.metrobuzz.data.scene.basemap.Edge;
import ch.ethz.fcl.metrobuzz.data.scene.basemap.Node;
import ch.ethz.fcl.metrobuzz.data.singapore.SGMRTStations;

/**
 * find all non-cyclical paths (simple paths
 * http://xlinux.nist.gov/dads//HTML/allSimplePaths.html) between two nodes in a
 * graph
 * 
 * @author Zeng Wei
 * @email zeng@arch.ethz.ch
 * 
 */
public class AllSimplePaths {
	private static List<Path> simplePathList;

	private static final boolean DEBUG = true;

	public static List<Path> getAllSimplePaths(MBData data, Node source,
			Node end) {
		List<Node> allNodes = data.getScene().getNodes();

		simplePathList = new ArrayList<Path>();
		if (!allNodes.contains(source) || !allNodes.contains(end))
			return simplePathList;

		List<Node> visited = new ArrayList<Node>();
		visited.add(source);
		depthFirst(data, source, end, visited);

		Collections.sort(simplePathList, new Comparator<Path>() {
			@Override
			public int compare(Path p1, Path p2) {
				if (p1.getCost() > p2.getCost())
					return 1;
				else
					return -1;
			}
		});

		simplePathList = filterPaths(simplePathList);

		if (DEBUG) {
			// List<Float> possibilities = pathPossibility(simplePathList);
			// System.out.println("From " + source.getId() + " to " +
			// end.getId()
			// + " all simple paths:");
			// for (int i = 0; i < simplePathList.size(); i++) {
			// Path sp = simplePathList.get(i);
			// float possibility = possibilities.get(i);
			// System.out.println(sp.toString() + " "
			// + MBTools.formatTimeInSeconds(sp.getCost())
			// + " possibility " + possibility);
			//
			// }

			// if (simplePathList.size() == 0)
			// System.out.println(source.getId() + "->" + end.getId()
			// + " is N.A.");
		}

		return simplePathList;
	}

	private static void depthFirst(MBData data, Node current, Node end,
			List<Node> visited) {
		List<Edge> oEdges = current.getOutEdges();

		int waitingTime = 20; // wait 20 secs at every station

		for (Edge e : oEdges) {
			Node eEnd = e.getEndNode();
			if (visited.contains(eEnd))
				continue;

			if (eEnd.equals(end)) {
				visited.add(eEnd);

				Path p = new Path();
				p.addPath(visited.get(0), waitingTime);

				for (int i = 1; i < visited.size(); i++) {
					Node node = visited.get(i);
					Node preNode = visited.get(i - 1);

					// distance in meters of the two nodes
					float distance = data.getScene().getBound()
							.getWorldDist(node.distance(preNode));
					// time cost assuming MRT speed is 40 km/h
					float time = distance / 1000 / 40 * 3600;

					if (i < visited.size() - 1) {
						Node nextNode = visited.get(i + 1);
						boolean sameLine = SGMRTStations.isSameLine(preNode,
								node, nextNode);
						if (!sameLine) // if not on the same line, add waiting
										// time of four minitues
							time += 240;
					}

					time += waitingTime;
					p.addPath(node, time);
				}

				simplePathList.add(p);

				// System.out.println(p);
				visited.remove(visited.size() - 1);

				break;
			}
		}

		for (Edge e : oEdges) {
			Node eEnd = e.getEndNode();
			if (visited.contains(eEnd) || eEnd.equals(end))
				continue;

			visited.add(eEnd);

			// System.out.println("visiting " + eEnd.getId());
			depthFirst(data, eEnd, end, visited);

			visited.remove(visited.size() - 1);
		}
	}

	/**
	 * filter possible paths with the cost less than 130% cost of the minimum
	 * cost from all possible paths.
	 * 
	 * 
	 * @param allSimplePaths
	 * @return
	 */
	private static List<Path> filterPaths(List<Path> allSimplePaths) {
		float threshold = 1.2f;

		List<Path> filterPaths = new ArrayList<Path>();
		if (allSimplePaths.size() == 0)
			return filterPaths;
		else {
			float minCost = allSimplePaths.get(0).getCost();
			for (int i = 0; i < allSimplePaths.size(); i++)
				if (allSimplePaths.get(i).getCost() <= threshold * minCost)
					filterPaths.add(allSimplePaths.get(i));
		}
		return filterPaths;
	}

	public static List<Float> pathPossibility(List<Path> possiblePaths) {
		List<Float> possibilities = new ArrayList<Float>();

		if (possiblePaths.size() == 1) {
			possibilities.add(new Float(1));
		} else {
			float allCost = 0;
			for (int i = 0; i < possiblePaths.size(); i++)
				allCost += possiblePaths.get(i).getCost();

			for (int i = 0; i < possiblePaths.size(); i++) {
				float poss = (allCost - possiblePaths.get(i).getCost())
						/ allCost / (possiblePaths.size() - 1);

				possibilities.add(poss);
			}
		}

		return possibilities;
	}
}
